#pragma once
#include <iostream>
#include <fstream>
#include <list>
#include <string>
#include <vector>
#include <ctime>
#include <memory>
#include <chrono>
#include <iomanip>
#include <algorithm>
#include <cstdint>
#include <unordered_map>
#include "log.hpp"

// 读取文件格式
enum class FileFormat
{
    TEXT,  // 文本文件
    BINARY // 二进制文件
};

// 主服务选择
enum
{
    EXIT = 0, // 退出系统
    READ,     // 读取文件服务
    SORT,     // 排序服务
    SEARCH,   // 查找服务
    UPDATE    // 更新(写文件服务)
};

// 排序服务选择
enum
{
    InsertSort = 1, // 插入排序
    ShellSort,      // 希尔排序
    SelectSort,     // 选择排序
    BubbleSort,     // 冒泡排序
    QuickSort,      // 快速排序
    MergeSort       // 归并排序
};
// 查找服务选择
enum
{
    Order = 1, // 遍历查找
    Binary,    // 二分查找
    Hash,      // 哈希查找
    SearchTree // 二叉搜索树查找
};
// 更新服务选择
enum
{
    AddRecord = 1, // 添加记录
    DeleteRecord,  // 删除记录
    ModifyRecord,  // 修改记录
};

typedef unsigned char INT8U;
typedef signed char INT8S;
typedef unsigned short INT16U;
typedef signed short INT16S;
typedef unsigned long INT32U;
typedef signed long INT32S;

typedef class ListNode
{
public:
    ListNode() {}
    ListNode(INT16U usRecSize, INT32U ulLinkID, INT16U usRoadNameSize, INT32U ulStaNodeInfo, const std::string &pcRoadName)
        : _usRecSize(usRecSize), _ulLinkID(ulLinkID), _usRoadNameSize(usRoadNameSize), _ulStaNodeInfo(ulStaNodeInfo), _pcRoadName(pcRoadName)
    {
    }
    INT16U _usRecSize;       // 记录的Size
    INT32U _ulLinkID;        // LinkID
    INT16U _usRoadNameSize;  // 道路名称的Size
    INT32U _ulStaNodeInfo;   // 始点Node信息
    std::string _pcRoadName; // 道路名称
} Node;

class MapSystem
{
public:
    MapSystem()
        : _input(0), _flag(true)
    {
        _log.Enable(ScreenAndFile); // 日志既向屏幕输出,也向文件输出
    }

    // 提供主系统服务
    void Main_Service();

public:
    /* 菜单服务模块 */
    void _DisPlayMenu(); // 显示主菜单
    bool _Input();       // 选择服务
    void _ExitCase();    // 退出系统
    void _ErrorCase();   // 选择服务错误情况处理

    /* 文件服务模块 */
    void _DisPlayFileSelectMenu();     // 显示选择文件菜单
    FileFormat _SelectFileFormat();    // 用户选择文件格式
    void _ReadFile(FileFormat);        // 提供文件服务
    bool _ReadTextFile();              // 文本文件读取
    bool _InputFile();                 // 文本文件写入
    bool _ReadBinaryFile();            // 二进制文件读取
    bool _OutputBinaryFile();          // 二进制文件写入
    inline INT16U _swapEndian(INT16U); // 字节序转换函数
    inline INT32U _swapEndian(INT32U); // 字节序转换函数
    bool _WriteFile();                 // 更新数据并写入文件

    /* 排序模块 */
    void _DisPlaySortMenu();                                 // 显示排序选择菜单
    void _SortService();                                     // 提供排序服务
    void _ListToVector();                                    // 初始化数组
    std::vector<Node> &_InsertSort_Implement();              // 插入排序
    std::vector<Node> &_ShellSort_Implement();               // 希尔排序
    std::vector<Node> &_SelectSort_Implement();              // 选择排序
    std::vector<Node> &_BubbleSort_Implement();              // 冒泡排序
    std::vector<Node> &_QuickSort_Implement(size_t, size_t); // 快速排序
    std::vector<Node> &_MergeSort_Implement(size_t, size_t); // 归并排序

    /* 索引模块 */
    void _DisPlaySearchMenu();                                          // 显示查找菜单
    void _SearchService();                                              // 提供查找服务
    void _InputSearch(INT32U &);                                        // 查找记录ID输入
    std::vector<Node>::iterator _SearchWithOrder(INT32U);               // 遍历查找
    std::vector<Node>::iterator _SearchWithBinary(INT32U);              // 二分查找
    std::unordered_map<INT32U, Node>::iterator _SearchWithHash(INT32U); // 哈希查找
    std::vector<Node>::iterator _SearchWithTree(INT32U);                // 二叉排序树查找

    /* 更新模块 */
    void _DisPlayUpdataMenu();                             // 显示更新服务菜单
    void _UpdataService();                                 // 提供更新数据服务
    bool _CheckLinkID(int &);                              // 检查用户输入linkID的合法性
    int _GetOption();                                      // 检查用户选择的操作是否合法
    std::vector<Node>::iterator _FindVectorRecord(INT32U); // 查找linkID的记录（数组）
    std::list<Node>::iterator _FindListRecord(INT32U);     // 查找linkID的记录（链表）
    void _AddRecord();                                     // 添加记录
    void _DeleteRecord();                                  // 删除记录
    void _ModifyRecord();                                  // 修改记录

private:
    Log _log;                        // 日志对象
    size_t _input;                   // 选择服务项
    bool _flag;                      // 判断是否退出服务
    std::list<Node> _nodeList;       // 存放结点的链表
    std::vector<Node> _vector_array; // 存放结点的数组
};

// 二叉排序树的节点
class TreeNode
{
public:
    Node data;                       // 数据
    std::shared_ptr<TreeNode> left;  // 左子树
    std::shared_ptr<TreeNode> right; // 右子树

    TreeNode(const Node &node) : data(node), left(nullptr), right(nullptr) {}
};
// 二叉排序树
class BinarySearchTree
{
public:
    BinarySearchTree() : root(nullptr) {}

    // 插入新节点
    void Insert(const Node &node)
    {
        root = _Insert(root, node);
    }
    // 查找节点
    Node *Search(INT32U linkID)
    {
        return _Search(root, linkID);
    }

private:
    std::shared_ptr<TreeNode> root;
    // 递归插入新节点
    std::shared_ptr<TreeNode> _Insert(std::shared_ptr<TreeNode> node, const Node &newNode)
    {
        if (node == nullptr)
            return std::make_shared<TreeNode>(newNode); // 如果当前节点为空，创建新节点

        if (newNode._ulLinkID < node->data._ulLinkID)
            node->left = _Insert(node->left, newNode); // 插入到左子树
        else if (newNode._ulLinkID > node->data._ulLinkID)
            node->right = _Insert(node->right, newNode); // 插入到右子树

        return node; // 返回当前节点
    }
    // 递归查找节点
    Node *_Search(std::shared_ptr<TreeNode> node, INT32U linkID)
    {
        if (node == nullptr || node->data._ulLinkID == linkID)
            return node ? &node->data : nullptr; // 找到返回节点数据，未找到返回空指针

        if (linkID < node->data._ulLinkID)
            return _Search(node->left, linkID); // 在左子树中查找
        else
            return _Search(node->right, linkID); // 在右子树中查找
    }
};